#pragma once
#include <algorithm>
#include <vector>

//////////////////////////////////////////////////////////////////////////
//

namespace umtl
{
	template< typename DataType, typename CompareType = std::less< DataType > >
	class priority_vector
	{
	public:
		typedef std::vector< DataType >				container_type;
		typedef CompareType							compare_type;
		typedef typename container_type::iterator	iterator;

		priority_vector() 
			: sorted_(false)
		{}

		inline size_t capacity() const {
			return container_.capacity();
		}

		inline void reserve(size_t n) {
			return container_.reserve(n);
		}

		inline size_t size() const {
			return container_.size();
		}

		inline bool empty() const {
			return container_.empty();
		}

		inline void push( DataType & data ) {

			make_heap();

			container_.push_back( data );

			std::push_heap( container_.begin(), container_.end(), comp_operator_ );
		}

		inline DataType pop() {

			make_heap();

			std::pop_heap( container_.begin(), container_.end(), comp_operator_ );

			DataType back = container_.back();

			container_.pop_back();

			return back;
		}

		inline void clear() { 

			container_.clear();
		};

		inline iterator begin() {

			sort();

			return container_.begin();
		};

		inline iterator end() { 

			sort();

			return container_.end();
		};

		inline void sort() {

			if( !sorted_ )
			{
				std::sort( container_.begin(), container_.end(), comp_operator_ );
				sorted_ = true;
			}
		}

		inline void make_heap() {

			if( !container_.empty() && sorted_ )
			{
				std::make_heap( container_.begin(), container_.end(), comp_operator_ );
				sorted_ = false;
			}
		}

	private:
		container_type container_;
		compare_type comp_operator_;
		bool sorted_;
	};
}

//////////////////////////////////////////////////////////////////////////